//2009/08/01 20:36:39
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;

class WordParts
{
public:
    int partCount(string original, string compound)
    {
		int n = original.size();
		int m = compound.size();
		int l;
		for(int i=1; i<=n; i++)
			s.insert(original.substr(0, i));
		for(int i=1; i<=n; i++)
			s.insert(original.substr(n-i, i));
		vector<int> mem(m+1, 1000);
		mem[m] = 0;
		for(int i=m-1; i>=0; i--)
		{
			for(__typeof(s.begin()) j=s.begin(); j!=s.end(); j++)
			{
				if(i+(l=(*j).size()) <= m && compound.substr(i,l) == *j)
					mem[i] = min(mem[i], mem[i+l] + 1);
			}
		}
		return mem[0]==1000 ? -1 : mem[0];
    }
private:
    set<string> s;
};
